\documentclass[submission]{FPSAC2017}

\articlenumber{84}
\addbibresource{84_Aguiar_Chan.bib}

\usepackage[newitem,newenum,neverdecrease]{paralist}
\usepackage{verbatim}
\usepackage{color}
\usepackage{url}
\usepackage{enumerate}
\usepackage{lineno,xcolor}
\usepackage{graphicx} 
\usepackage{tikz}
\usetikzlibrary{shapes,positioning,patterns}

\usepackage{standalone} %to externalize tikz load
\usepackage{mathrsfs} %to use \mathscr


%miscellaneous commands
\newcommand{\outdeg}{\text{outdeg}}%outdegree of a vertex
\newcommand{\indeg}{\text{indeg}}%indegree of a vertex
\DeclareMathOperator{\lbl}{\text{lbl}}% label
\DeclareMathOperator{\ess}{\text{ess}}% essentialization of a hyperplane arrangement
\DeclareMathOperator{\gsf}{\mathsf{g}}% g-index of a partition
\DeclareMathOperator{\inset}{\textnormal{in}}% inset of a vertex
\DeclareMathOperator{\outset}{\textnormal{out}}% outset of a vertex


\DeclareMathOperator{\lcm}{lcm}
\newcommand{\internal}{\text{in}}%internal activities of a forest
\newcommand{\external}{\text{ex}}%external activities of a forest


%symbols
\newcommand{\chit}{\overline{\chi}} %toric characteristic polynomial
\newcommand{\st}{\mathsf{st}} % standard weight function
\newcommand{\Tc}{\mathcal{T}} % quasi Tutte polynomial
\newcommand{\wt}{\mathsf{wt}} % weight function
\newcommand{\Ml}{\overline{M}} % arithmetic Tutte polynomial
\newcommand{\Gcr}{\mathscr{G}} % weighted graph
\newcommand{\Fcr}{F} % spanning forest


\newcommand{\ab}{\mathbf{a}} % vector
\newcommand{\eb}{\mathbf{e}} % vector
\newcommand{\hb}{\mathbf{h}} % vector


%sets
\newcommand{\Nb}{\mathbb{N}} %natural number
\newcommand{\Zb}{\mathbb{Z}} %integers 
\newcommand{\Rb}{\mathbb{R}} %reals 

\newcommand{\Gc}{ \mathcal{G}} %weighted graph
\newcommand{\Hc}{ \mathcal{H}} %hyperplane arrangement
\newcommand{\Ac}{ \mathcal{A}} % linear hyperplane arrangement
\newcommand{\Cc}{ \mathcal{C}} % linear chambers
\newcommand{\Aca}{ \widetilde{\mathcal{A}}} % affine hyperplane arrangement
\newcommand{\Cca}{ \widetilde{\mathcal{C}}} %affine chambers
\newcommand{\Act}{ \overline{\mathcal{A}}} % toric hyperplane arrangement
\newcommand{\Cct}{ \overline{\mathcal{C}}} %toric chambers

\newcommand{\lat}{\mathcal{L}} %lattice

\newcommand{\Hct}{ \widetilde{\mathcal{H}}} % affine hyperplane arrangement
\newcommand{\Pct}{ \widetilde{\mathcal{P}}} % affine intersection poset


\newcommand{\Hcl}{ \overline{\mathcal{H}}} % toric hyperplane arrangement
\newcommand{\Pcl}{ \overline{\mathcal{P}}} % toric intersection poset

\newcommand{\Pit}{ \overline{\Pi}} %intersection poset



\newcommand{\Ps}{\mathscr{P}} %combinatorial poset 
\newcommand{\Oc}{\mathcal{O}} %Orientation 

\newcommand{\Hl}{ \overline{H}} %toric hyperplane
\newcommand{\Tl}{\overline{T}} % toric subspace
\newcommand{\Ul}{\overline{U}} % toric subspace
\newcommand{\Vl}{\overline{V}} % geometric torus
\newcommand{\Wl}{\overline{W}} % geometric torus

\newcommand{\Ht}{\widetilde{H}} % affine hyperplane
\newcommand{\Tt}{\widetilde{T}} % affine subspace
\newcommand{\Ut}{\widetilde{U}} % affine subspace

\newcommand{\Lh}{\widehat{L}} % dual lattice
\newcommand{\Proj}{ \text{Proj}} %Proj


\newcommand{\Sc}{\mathcal{S}} %signed partition

\newcommand{\xt}{\widehat x} % element in a poset


\newcommand{\qand}{\quad\text{and}\quad}
\newcommand{\qqand}{\qquad\text{and}\qquad}
\newcommand{\qor}{\quad\text{or}\quad}
\newcommand{\qqor}{\qquad\text{or}\qquad}

\newcommand{\blue}[1]{\textcolor{blue}{#1}}
\newcommand{\red}[1]{\textcolor{red}{#1}}
\newcommand{\green}[1]{\textcolor{green}{#1}}
\newcommand{\black}[1]{\textcolor{black}{#1}}


\newcommand{\map}[1]{\xrightarrow{#1}}
\newcommand{\abs}[1]{\lvert#1\rvert}    % absolute value
\newcommand{\norm}[1]{\lVert#1\rVert} % norm
\newcommand{\br}[1]{\langle #1\rangle} % bilinear form


\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\Hom}{Hom}

\DeclareMathOperator{\Frst}{\text{SF}} % set of spanning forests
\DeclareMathOperator{\spin}{\gcd} %spin for partition lattice
\DeclareMathOperator{\Vor}{\textnormal{Vor}} % Voronoi cell
\DeclareMathOperator{\Cham}{\textnormal{Cham}} % set of chambers of arrangements
\DeclareMathOperator{\Chaml}{\overline{\textnormal{Cham}}} % set of toric chambers of arrangements
\DeclareMathOperator{\Acyc}{\textnormal{Acyc}} % set of acyclic orientations


\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}


\theoremstyle{definition}
\newtheorem{examplex}{Example}[section]
\newenvironment{example}
  {\pushQED{\qed}\renewcommand{\qedsymbol}{$\triangle$}\examplex}
  {\popQED\endexamplex}


\usepackage{lipsum}

\title[Graphic toric arrangements]{Toric arrangements associated to graphs}

\author{Marcelo Aguiar\thanks{Aguiar supported in part by NSF grant DMS-140111.}\addressmark{1} \and Swee Hong Chan\addressmark{2}}

\address{Department of Mathematics, Cornell University, Ithaca, NY 14853}

\received{November 14, 2016}

\abstract{We study certain toric arrangements associated to graphs. The arrangement depends on the choice of an integral lattice: we focus on the case of the (co)root lattice of type $A$, but also comment on the (simpler) case of the (co)weight lattice of type $A$.
We obtain a combinatorial description for the intersection poset and derive several results on the characteristic polynomial and the arithmetic Tutte polynomial of the toric arrangement. The former counts proper colorings that satisfy an additional divisibility condition.
By employing the Voronoi cell of the lattice, we show that the
chambers of certain toric arrangements may be seen as equivalence classes for a canonical equivalence relation on the set of chambers of the corresponding linear arrangement. We study this relation in the graphic case.}

\keywords{Toric arrangement, root system, graphic arrangement, Tutte polynomial, Voronoi cell, acyclic orientation}

\begin{document}

\maketitle

\section{Introduction}
We study arrangements of hypertori in a torus. Such an arrangement is associated to a set of integral vectors with respect to a lattice. We set up the relevant notions in \cref{s:toric-arr}.
In \cref{s:toric-graphic} we discuss certain toric arrangements associated to a simple graph.
The (co)root and (co)weight lattices of type $A$ furnish the other necessary ingredient. The latter case exhibits a simpler behavior. We focus on the former for the most part. \cref{s:toric flats} deals with the intersection poset. Our first result provides a combinatorial description for this poset. These are followed by results on the characteristic and arithmetic Tutte polynomials in \cref{s:char-tutte}. They include an expression for the former in terms of certain proper colorings, the introduction of the $d$-divisible Tutte polynomial, an expression for this polynomial in terms of activities, and a formula relating it to the arithmetic Tutte polynomial. In \cref{s:voronoi} we introduce a canonical equivalence relation on the set of chambers of a linear arrangement. This relation depends on the lattice and is defined when the Voronoi cell is \emph{confined} by the affine arrangement. We conclude by analyzing this relation in the case of graphic arrangements in \cref{s:voronoi-graphic}. 

\section{Toric arrangements}\label{s:toric-arr}
Let $V$ be a real vector space of finite dimension $d$. Fix an inner product $\langle \cdot,\cdot\rangle$ in $V$. For each $\alpha\neq 0$ in $V$, and each $k\in\Rb$, let
\[
H_\alpha := \{x\in V \mid \langle\alpha,x\rangle=0\} \qand
H_{\alpha,k} := \{x\in V \mid \langle \alpha, x\rangle=k\}.
\]
Then $H_\alpha$ is a \emph{linear hyperplane} in $V$, while 
$H_{\alpha,k}$ is an \emph{affine hyperplane} in $V$. 
View $V$ as an abelian group under addition. Each linear hyperplane $H_\alpha$ is then a subgroup, and  each affine hyperplane $H_{\alpha,k}$ is a coset for this subgroup.

A \emph{lattice} $L$ in $V$ is a subgroup of $V$ generated by a basis of $V$.
It is free abelian of rank $d$. 
The associated $d$-dimensional \emph{torus}  is the quotient group $T:=V/L$. 
A \emph{linear hypertorus} is a subgroup of $V/L$ that is isomorphic to a $(d-1)$-dimensional torus, and  an \emph{affine hypertorus} is a coset in $V/L$ of a linear hypertorus.

The \emph{dual lattice} of $L$ is
$\Lh := \{\alpha\in V \mid \text{ $\langle \alpha, \lambda\rangle\in\Zb$ for all $\lambda\in L$}\}$. It is a lattice in $V$.


A linear hyperplane $H$ in $V$ is \emph{$L$-integral} if there is $\alpha\in\Lh$ such that $H=H_\alpha$.
Given a hyperplane $H$ in $V$, or more generally a subset $H$ of $V$, let $\Hl$ denote the image of $H$ in $V/L$ under the canonical projection.
If $H$ is an $L$-integral linear hyperplane in $V$, then $\Hl$ is a linear hypertorus in $V/L$.
It follows that for any coset $H+x$ of $H$, its image $\Hl+\overline{x}$ is an affine hypertorus in $V/L$.



A vector $\alpha$ is \emph{$L$-integral} if it belongs to $\Lh$.
Let $\Phi$ be a finite set of nonzero $L$-integral vectors. To this data we associate two hyperplane arrangements in $V$, one linear and the other affine:
\[
\Ac(\Phi) := \{H_\alpha \mid \alpha\in \Phi\}
\qand
\Aca(\Phi) := \{H_{\alpha,k} \mid \alpha\in \Phi,\,k\in\Zb\}.
\]
The associated \emph{toric} arrangement in $V/L$ is
\[
\Act(\Phi,L) := \{\Hl_{\alpha,k} \mid \alpha\in \Phi,\,k\in\Zb\}.
\]
It consists of affine hypertori in $V/L$. Integrality guarantees that $\Act(\Phi,L)$ is finite.
If $\Phi$ generates $V$ over $\Rb$, 
the arrangement $\Ac(\Phi)$ is \emph{essential}. In this case, the minimal flats of each arrangement are zero-dimensional.  

\begin{example}
Let $V=\Rb^d$ with the standard inner product and let $L=\Zb^d$. Any set of nonzero vectors $\Phi\subseteq \Zb^d=\Lh$ yields a toric arrangement in the \emph{standard torus} $V/L$.
\end{example}

\begin{example}\label{example: coweight}
Let $\Phi$ be a crystallographic root system in $V$~\cite[Section~1.2]{Hump90}. 
The root lattice is $\Zb\Phi$ and its dual $L=\widehat{\Zb\Phi}$ is the coweight lattice of $\Phi$.
Then $\Phi\subseteq \Lh$ and we obtain a toric arrangement $\Act(\Phi,L)$ in $V/L$.
\end{example}

\begin{example}\label{example: Steinberg torus}
Let $\Phi$ be as before, $\Phi^\vee$ the set of coroots, and $L=\Zb\Phi^\vee$, the coroot lattice of $\Phi$. Then $\Lh$ is the weight lattice of $\Phi$ and
the crystallographic assumption states that $\Phi\subseteq \Lh$.
Then $\Act(\Phi,L)$ is a toric arrangement in the \emph{Steinberg torus} $V/L$ of $\Phi$. It is studied in~\cite{AP15,DPS09}.
\end{example}

 
\section{Toric arrangements associated to a graph}\label{s:toric-graphic}

Let $\{e_i\}_{1\leq i\leq n}$ be the standard basis of $\Rb^n$. For $n\geq 2$, consider
\[
A_{n-1}:=\{ e_i-e_j \mid 1\leq i \neq j \leq n\} \qand V_n:=\{(x_1,\ldots,x_n) \in \Rb^n \mid x_1+\ldots+x_n=0 \}.
\]
The former is a root system (of type $A$) and the latter is the subspace of $\Rb^n$ it spans. $\Rb^n$ is endowed with the standard inner product and $V_n$ with the induced one. For root systems of type $A$, there is no distinction between roots and coroots, or between weights and coweights.

Given a simple graph $G$ with with vertex set $V(G)=[n]$ and edge set $E(G)$, consider the subset $\Phi_G$ of $A_{n-1}$ given by
\[
\Phi_G:=\{e_i-e_j \mid  \{i,j\} \in E(G)\}. 
\]
There are three toric arrangements naturally associated to $G$,
given by different choices for the space $V$ and the lattice $L$. (In all three cases, $\Phi_G \subseteq \widehat{L}$).

\begin{enumerate}[(i)]
\item \label{item: standard graphic arrangement}  
$V=\Rb^n$ and $L=\Zb^n$. Then $\Act(\Phi_G,L)$ sits in the standard torus. This arrangement is studied in \cite{DMR16,ERS09,NPS02}.

\item \label{item: coweight graphic arrangement}  
$V=V_n$ and $L=\widehat{\Zb A_{n-1}}=\Zb\{\frac{1}{n}(e_1+\ldots+e_n) -e_i \mid 1\leq i \leq n \}$ the (co)weight lattice of $A_{n-1}$.
The arrangement $\Act(\Phi_G,L)$ turns out to be the essentialization of the arrangement in \eqref{item: standard graphic arrangement}. With the exception of a few remarks (notably in \cref{p:Voronoi-coweight}), we do not pursue its study in this note.

\item \label{item: coroot graphic arrangement}  
$V=V_n$ and $L=\Zb A_{n-1}$ the (co)root lattice of $A_{n-1}$.
The arrangement $\Act(\Phi_G,L)$ sits in the Steinberg torus of $A_{n-1}$.
This note focuses on combinatorial aspects of this arrangement and the more general family of arrangements introduced next.
\end{enumerate}

\begin{figure}[!h]
\centering
   \includegraphics[width=\textwidth]{figures/Steinberg_joined_graphic_arrangement}
\caption{(a) The positive roots of $A_2$. (b) The affine arrangement of the complete graph $K_3$, with the linear arrangement in boldface. 
 (c) The Steinberg torus of $A_{2}$. Note the identifications along the boundary.
 (d) The toric arrangement consists of $3$ circles. 
 }
\label{figure:Steinberg_joined_graphic_arrangement}
\end{figure}




A \emph{weighted graph} $\Gcr=(G,\wt)$ consists of a simple graph $G$ with $V(G)=[n]$ and a \emph{weight function}
\[
\wt:V(G) \to \Zb_{>0},
\]
which associates a positive integer to each vertex of $G$. (These differ from the graphs in \cite[Section 9]{BM14}, which carry weighted edges.) Given such $\Gcr$, let
\begin{align*}
V_{\Gcr} & := \{(x_1,\ldots, x_n)\in \Rb^n \mid \wt(1)x_1+\ldots \wt(n)x_n=0\},\\
\langle x,y\rangle_{\Gcr} & := \wt(1)x_1y_1+\ldots+\wt(n)x_ny_n,\\
\Phi_{\Gcr} & := \left\{\frac{e_i}{\wt(i)}-\frac{e_j}{\wt(j)} \mathrel{\Big|}  \{i,j\} \in E(\Gcr) \right\},\\
L_{\Gcr} & := \Zb\left\{ \frac{\wt(j)e_i-\wt(i)e_j}{\gcd(\wt(i),\wt(j))} \mathrel{\Big|}  1 \leq i\neq j \leq n\right\}.
\end{align*}
The resulting toric arrangement $\Act(\Phi_\Gcr,L_{\Gcr})$ is studied in \cref{s:char-tutte}. When the weight of every vertex is $1$, this arrangement reduces to the one in \eqref{item: coroot graphic arrangement} above.

\begin{figure}[!ht]\label{figure:weighted graph arrangement}
\centering
   \includegraphics[width=0.75 \linewidth]{figures/W_graph_arr_K_3_(1,1,2)}
   \caption{(a) The affine arrangement of the complete graph $K_3$ with weights $\wt(1)=\wt(2)=1$, $\wt(3)=2$.
   (b) The corresponding toric arrangement.}  
\end{figure}
 
 \section{Intersection poset of toric graphic arrangements}\label{s:toric flats}

Fix $L$ and $\Phi$ as in \cref{s:toric-arr}. An \emph{affine flat} is a nonempty intersection of affine hyperplanes in $\Aca(\Phi,L)$.
A \emph{toric flat} is the image of an affine flat in the torus $V/L$.
Equivalently, a toric flat is a connected component in a nonempty intersection of hypertori in $\Act(\Phi,L)$.
The intersection of two toric flats (in particular, two hypertori) is in general not a toric flat, but instead a disjoint union of toric flats.

The \emph{intersection poset} $\Pit(\Phi,L)$ is the set of all toric flats of 
$\Act(\Phi,L)$, ordered by  inclusion.
The poset  $\Pit(\Phi,L)$  is graded. When the arrangement is essential, the rank of a flat is its topological dimension. There is a maximum element (the ambient torus $T:=V/L$) and several minimal elements (points when the arrangement is essential).


\begin{figure}[!h]\label{figure:intersection_poset_A2}
\centering
   \includegraphics[width=0.45 \linewidth]{figures/Intersection_poset_A2}
   \caption{(a) The arrangement $\Act(\Phi_{K_3},\Zb A_2)$, with flats distinguished by color.
Any two one-dimensional flats intersect in the same three points.
   (b) The intersection poset.}  
\end{figure}



Let $G$ be a simple graph. Consider the arrangement $\Act(\Phi_{G},\Zb A_{n-1})$
as in \cref{s:toric-graphic}, item \eqref{item: coroot graphic arrangement}.
We turn to a combinatorial description of its intersection poset.

For any partition $\pi=\{B_1,\ldots, B_k\}$ of $[n]$, let  
\[
\spin (\pi):=\gcd \{|B_i| \mid 1 \leq i \leq k\}.
\]
We order the partitions of $[n]$ by refinement: $\pi \leq \pi'$ if each block of $\pi'$ is contained in a block of $\pi$. In this case, $\spin(\pi')$ divides $\spin(\pi)$.

A partition $\pi$ is a \emph{bond} of $G$ if the graph induced by $G$ on each block of $\pi$ is connected.
Let  $\Pit(G)$ be the set of pairs $(\pi,t)$ where $\pi$ is a bond of $G$ and $t \in \Zb_{\spin(\pi)}$ is an integer modulo $\spin(\pi)$. This set is partially ordered by
\[
(\pi,t)\leq (\pi',t') \qquad \text{if $\pi\leq \pi'$ in $\Pi(G)$ and $t\equiv t'$ mod $\spin(\pi')$}.
\]
When $\pi'$ refines $\pi$,  $\spin(\pi')$ divides $\spin(\pi)$, and hence $t$ modulo  $\spin(\pi')$ is well-defined.

\begin{theorem}\label{theorem: the intersection poset of coroot toric graphic arrangements}
The poset $\Pit(G)$ is the intersection poset of the toric arrangement $\Act(\Phi_{G},\Zb A_{n-1})$.
\end{theorem}

The correspondence is as follows.
For any $(\pi,t)\in \Pit(G)$, choose a block $B$ of $\pi$, and choose $S_1, S_2 \subseteq B$ such that $|S_2|=t$ and $B=S_1 \sqcup S_2$.
The pair $(\pi,t)$ is identified with the image of the affine flat determined by the equalities:
\begin{align*} 
x_i=x_j \quad &\text{if $i,j$ belong to the same block of $\pi$ and $i,j \notin B$},\\
x_i=x_j \quad &\text{if $i,j\in S_1$ or $i,j\in S_2$},\\
x_i=x_j+1 \quad  &\text{if $i\in S_1$ and $j\in S_2$.} \qedhere
\popQED
\end{align*}

By contrast, the intersection poset of the standard arrangement of $G$ (\cref{s:toric-graphic}, item \eqref{item: standard graphic arrangement}) is simply the poset of bonds of $G$~\cite{NPS02}.

There is a similar model for the poset of toric \emph{faces} of $\Act(\Phi_{G},\Zb A_{n-1})$, which we do not discuss in this note. When $G$ is the complete graph, this
recovers the model given in~\cite[Section 4.3]{AP15}.
The combinatorial model for the toric flats of $\Act(\Phi_{K_3},\Zb A_{2})$ is shown in \cref{figure:Flats labeling A2} and may be compared to \cite[Figure 19]{AP15}.

\begin{figure}[!h]
\centering
   \includegraphics[width=0.5 \linewidth]{figures/Flats_labeling_A2}
\caption{The flats of the arrangement $\Act(\Phi_{K_3},\Zb A_2)$ with labels from $\Pit(G)$.
} 
\label{figure:Flats labeling A2}
\end{figure}


 
\section{Characteristic and Tutte polynomials}\label{s:char-tutte}

Fix $L$ and $\Phi$ as in \cref{s:toric-arr}.  The \emph{characteristic polynomial} of 
$\Act(\Phi,L)$ is
\[
\chit(\Phi,L;\,t):= \sum_{X \in \Pit(\Phi,L)} \mu(X,T) \, t^{\dim X},
\] 
where $\mu$ is the M\"{o}bius function of the intersection poset, $T$ is the torus $V/L$, and $\dim X$ is the dimension of the hypertorus $X$. Assume $\Phi$ spans $V$. A result of Zaslavsky \cite[Theorem 1.2]{Zas77} implies that $(-1)^{\dim T}\chit(\Phi,L;\,0)$ is the number of \emph{chambers} in $\Act(\Phi,L)$; see also \cite{ERS09,Des14,Moci12,NPS02}.

The \emph{arithmetic Tutte polynomial} of $\Act(\Phi,L)$, as defined by Moci~\cite{Moci12}, is 
\[
\Ml(\Phi,L;\,x,y):= \sum_{ A \subseteq \Phi} m(A) (x-1)^{\dim(\Phi)-\dim(A)}(y-1)^{|A|-\dim(A)},
\]
where $m(A)$ is the number of toric flats of $\Act(\Phi,L)$ given as an intersection of the form $ \bigcap_{\alpha \in A} \Hl_{\alpha, k_\alpha}$ ($k_{\alpha} \in \Zb$),
and $\dim(A)$ is the dimension of $\Rb$-span of $A$.
The characteristic polynomial is a specialization of the arithmetic Tutte polynomial~\cite[Theorem~5.6]{Moci12}:
\[
\chit(\Phi,L;\,t)= (-1)^{\dim(\Phi)}t^{\dim(T)-\dim(\Phi)}\Ml(\Phi,L;\,1-t,0).
\] 

 
Consider now a weighted graph $\Gcr=(G,\wt)$ and the corresponding toric arrangement $\Act(\Phi_\Gcr,L_{\Gcr})$, as in \cref{s:toric-graphic}. We turn to a combinatorial description of the
characteristic polynomial of this arrangement, which we denote by $\chit(\Gcr;\,t)$.



    A \emph{proper divisible coloring} of $\Gcr$ with $q$ colors is a function $f:V(G) \to \Zb_q$ such that
  \begin{itemize}
  \item $f(i)\neq f(j)$ whenever $i$ and $j$ are adjacent in $G$;
  \item $\sum_{i \in V(G)} \wt(i)f(i) \equiv 0 \mod q$.
  \end{itemize}
Write $\wt(\Gcr):=\wt(1)+\ldots + \wt(n)$
and $\gcd(\wt):= \gcd\{\wt(i) \mid i \in V(\Gcr)  \}$.

\begin{theorem}\label{theorem: characteristic poly as proper divisible colorings}
Let $\Gcr$ be a weighted graph with $\wt(\Gcr)=m$.
For  any positive multiple $q$ of $m$,
\[
\chit(\Gcr;\, q)=\frac{|\{\text{proper divisible coloring of $\Gcr$ with $q$ colors}\}|}{\gcd(\wt)}.  
\] 
\end{theorem}  
This result may be derived with the aid of the \emph{toric finite field method} \cite[Theorem~3.7]{ERS09}.

Let $\chit(G;\, t)$ denote the characteristic polynomial of 
$\Act(\Phi_G,\Zb A_{n-1})$. Specializing \cref{theorem: characteristic poly as proper divisible colorings} to the case when all weights are $1$, we see that $\chit(G;\, nt)$ counts proper divisible colorings of $G$. The following explicit expressions are worth-mentioning: for 
the path $P_n$ and the  star graph $K_{1,n-1}$ (both on $n$ vertices),
\[
\chit(P_n;\,t) = (-1)^{n-1} \sum_{d |n} \varphi(d) \left(1-t \right)^{\frac{n}{d}-1},\quad
\chit(K_{1,n-1};\,t) = (t-1)^{n-1}+(-1)^{n-1}(n-1),
\] 
where $\varphi$ is \emph{Euler's totient function}. Recall, by contrast, that
$P_n$ and $K_{1,n-1}$, as well as any other tree on $n$ vertices, have the same ordinary Tutte polynomial.

Let $K_n$ be the complete graph on $n$ vertices. The following formula, known from \cite[Theorem~1.19]{ACH15}, may also be derived from \cref{theorem: characteristic poly as proper divisible colorings}:
\[
\chit(K_n;\,t) = (-1)^{n-1}(n-1)! \sum_{d |n}(-1)^{\frac{n}{d}-1}  \varphi(d) \binom{\frac{t}{d}-1}{\frac{n}{d}-1}.
\]
Evaluating at $0$ we see that the number of chambers in the Steinberg torus $\Act(\Phi_{K_n},\Zb A_{n-1})$ is $n!$, as known from \cite{AP15,DPS09}.

We turn to the arithmetic Tutte polynomial of $\Act(\Phi_\Gcr,L_{\Gcr})$, denoted $\Ml(\Gcr;\, x,y)$.  
  
Given $d\in\Zb_{>0}$ and a subgraph $H$ of $G$, we say that $H$ is \emph{$d$-divisible}
  if the sum of the weights of the vertices in each connected component of $H$ is divisible by $d$.
We define the \emph{$d$-divisible Tutte polynomial} of $\Gcr$ as
\begin{align*}
T_d(\Gcr;\, x,y):= \sum_{\text{$H$ $d$-divisible}} (x-1)^{k(H)-k(G)}(y-1)^{\abs{H}+k(H)-\abs{V(G)}}. 
\end{align*}   
The sum is over the $d$-divisible subgraphs of $G$ and $k(H)$ is the number of connected components of $H$.\! When $d$ and all weights are $1$, \!$T_d$ is the ordinary\! Tutte polynomial of~$G$. 
  
  
\begin{theorem}\label{theorem: arithmetic Tutte polynomial as sums of divisible Tutte polynomial}
Let $\Gcr$ be a weighted graph with $\wt(\Gcr)=m$.
Then
\[  
\Ml(\Gcr;\,x,y)=\frac{1}{\gcd(\wt)}\sum_{d |m} \varphi(d)\,  T_d(\Gcr;\, x,y).
\]
\end{theorem}
By contrast, the arithmetic Tutte polynomial of the standard arrangement of $G$ (\cref{s:toric-graphic}, item \eqref{item: standard graphic arrangement}) is simply the Tutte polynomial of $G$~\cite{ERS09}.

In the special case when all weights are $1$, \cref{theorem: arithmetic Tutte polynomial as sums of divisible Tutte polynomial} may be derived from either \cref{theorem: the intersection poset of coroot toric graphic arrangements} or~\cite[Lemma~4.12]{ACH15}.

Recall that the ordinary Tutte polynomial admits an expression in terms of \emph{activities}. There exists an analogous result for the arithmetic Tutte polynomial due to D'Adderio and Moci~\cite{DM13}. We turn to a similar statement for the polynomial $T_d(\Gcr;\, x,y)$. 


Fix a positive integer $d$ and a total order on $E(G)$.
Let $\Fcr$ be a spanning forest of $G$.
An edge $e \in E(G) \setminus \Fcr$ is \emph{externally active} with respect to $F$ if $e$ is the smallest edge in the unique cycle of $\Fcr \cup \{e\}$. (This is the standard notion.)
We say that an edge $e \in \Fcr$ is \emph{$d$-internally active} with respect to $\Fcr$ if $\Fcr\setminus \{e\}$ is $d$-divisible and $e$ is the smallest edge in the cut  defined by $e$. (When $d=1$, this is the standard notion of internal activity.)
The \emph{external activity} of $\Fcr$, denoted by $\external(\Fcr)$, is the number of externally active edges with respect to $\Fcr$.
The \emph{$d$-internal activity} of $\Fcr$, denoted by $\internal_d(\Fcr)$, is the number of $d$-internally active edges with respect to $\Fcr$. Let $\Frst_d(\Gcr)$ denotes the set of spanning forests of $\Gcr$ that are $d$-divisible.
  
\begin{theorem}\label{theorem: divisible Tutte polynomial in terms of activities}
Let $\Gcr$ be a weighted graph and let $d$ be a positive integer.
Then
\[  
T_d(\Gcr;\,x,y)=\sum_{\Fcr \in \Frst_d(\Gcr)} x^{\internal_d(\Fcr)}y^{\external(\Fcr)}. \qedhere
\]
\end{theorem}  


  Our proof of \cref{theorem: divisible Tutte polynomial in terms of activities} uses a \emph{deletion-contraction recurrence} for divisible Tutte polynomials, which we do not describe in this note.
  
 
  

The following formulas may be derived as applications of \cref{theorem: arithmetic Tutte polynomial as sums of divisible Tutte polynomial,theorem: divisible Tutte polynomial in terms of activities} ($P_n$ is the path, $K_{1,n-1}$ the star, $C_n$ the cycle, and all weights are $1$).
\begin{align*}
\Ml(P_n;\,x,y) &= \sum_{d |n} \varphi(d)\, x^{\frac{n}{d}-1},\\
\Ml(K_{1,n-1};\,x,y) & = x^{n-1}+n-1,\\
\Ml(C_n;\,x,y) & = \sum_{d |n} d \, \varphi(d)\left(\frac{x^{\frac{n}{d}}-1}{x-1}  +\frac{y-1}{d}\right). 
\end{align*}


  \section{Voronoi equivalence}\label{s:voronoi}
  
 Let $\Phi$ and $L$ be as in \cref{s:toric-arr}.
We show that the chambers of certain toric arrangements $\Act(\Phi,L)$ may be seen as equivalence classes for a canonical equivalence relation on the set of chambers of the linear arrangement $\Ac(\Phi)$. 
  
The \emph{Voronoi cell} (at the origin) of $L$ is the polytope
\[
\Vor(L):=\{x \in V \mid \abs{x}\leq \abs{x-\lambda} \text{ for all $\lambda \in L$}\}. 
\]
It is a fundamental domain for the action of $L$ on $V$ by translations, so the torus $V/L$ may be realized as a quotient of $\Vor(L)$ in which boundary points are glued modulo $L$.

All hyperplanes in the linear arrangement $\Ac(\Phi)$ intersect the interior of $\Vor(L)$.
We say that $L$ is \emph{confined by $\Phi$} if no other hyperplane in the affine arrangement $\Aca(\Phi)$ intersects the interior of $\Vor(L)$.

\begin{figure}[!ht]
\centering
   \includegraphics[width=0.4\textwidth]{figures/Voronoi_confinement_modified}
\caption{The lattice $L$ (circles), its Voronoi cell $\Vor(L)$ (in blue), and the affine arrangement $\Aca(\Phi)$ (lines) for two choices of $L$ and $\Phi$, one confined, the other not.
(a)  $\Phi=\Phi_{P_3}$ and  $L=\Zb A_2$. (b) $\Phi=\Phi_{\Gcr}$ for $\Gcr$ the complete graph  $K_3$ with weights $\wt(1)=\wt(2)=1$, $\wt(3)=2$, and $L=L_{\Gcr}$.}
\label{figure:Voronoi_confinement}
\end{figure}

Assume that $L$ is confined by $\Phi$.
Note that $\Vor(L)$ is divided into regions by $\Ac(\Phi)$, one for each chamber of $\Ac(\Phi)$.
As $L$ is confined by $\Phi$ and $\Vor(L)$ is a fundamental domain of the torus $V/L$,
each of this region belongs to a toric chamber of $\Act(\Phi,L)$.
We say that two linear chambers  are \emph{Voronoi equivalent} if the corresponding regions in $\Vor(L)$ belong to the same toric chamber.
This defines an equivalence relation
on the set of linear chambers of $\Ac(\Phi)$, which we call \emph{Voronoi equivalence}.
By construction, Voronoi equivalence classes correspond to chambers of $\Act(\Phi,L)$.
\cref{figure:Voronoi_equivalence_example} illustrates the situation for 
the toric arrangement $\Act(\Phi_{P_3},\Zb A_2)$ of the path $P_3$.

\begin{figure}[!h]
\centering
   \includegraphics[width= 0.4\linewidth]{figures/Voronoi_equivalence_example}
\caption{
(a) Toric arrangement and Voronoi cell.
(b) Linear arrangement. The two chambers with the same pattern are Voronoi equivalent.}
\label{figure:Voronoi_equivalence_example}
\end{figure}


\begin{proposition}\label{p:confined}
When $\Phi$ is a crystallographic root system, both the coroot lattice $\Zb \Phi^\vee$ and the coweight lattice $\widehat{\Zb\Phi}$ are confined by $\Phi$.
\end{proposition}
The proof relies on the observation that the Voronoi cell of $\Zb \Phi^\vee$ is 
the largest confined neighborhood of the origin. 

\section{Voronoi equivalence for toric graphic arrangements}\label{s:voronoi-graphic}

We turn to the study of Voronoi equivalence for the toric arrangements 
$\Act(\Phi_G, \widehat{\Zb A_{n-1}})$ and $\Act(\Phi_G,\Zb A_{n-1})$ of \cref{s:toric-graphic}.
Confinement of its Voronoi cell follows from \cref{p:confined}. In each case, Voronoi equivalence is a relation on the set $\Cham(G)$ of chambers of the linear arrangement $\Ac(\Phi_G)$. 

We assume throughout this section that $G$ is connected. 
This guarantees that $\Phi_G$ spans and that $\Act(\Phi_G)$ is essential.
With minor adjustments, the results that follow can be extended to all simple graphs.

The set $\Cham(G)$ is in bijection with the set $\Acyc(G)$ of acyclic orientations of $G$ by the following correspondence~\cite{GZ83}:
an orientation $\Oc \in \Acyc(G)$ is associated to the chamber 
$C=\{ x \in V \mid  x_i< x_j  \text{ if $i \to j$ in $\Oc$}\}$. 
Through this correspondence, Voronoi equivalence is a relation on the set $\Acyc(G)$.

For the coweight lattice, Voronoi equivalence turns out to be a familiar relation.
A \emph{source-to-sink flip} is an operation that turns an acyclic orientation $\Oc$ into another $\Oc'$ by choosing a source vertex $i$ in $\Oc$, and then changing the orientation  in $\Oc$ of all edges incident to $i$. Then $i$ is a sink vertex in the new orientation $\Oc'$. See \cref{fig:source-to-sink} (a).

\begin{figure}[!h]
\center
   \includegraphics[width=0.7\linewidth]{figures/Source_sink_combined}
\caption{(a) A source-to-sink flip. (b) A source-sink exchange.}
\label{fig:source-to-sink}
\end{figure}


\begin{theorem}\label{p:Voronoi-coweight}
Let $L=\widehat{\Zb A_{n-1}}$.
Two orientations in $\Acyc(G)$ are Voronoi equivalent if and only if they are related by a sequence of source-to sink flips. 
\end{theorem}
This relation arose in \cite{Moses72} and \cite{Pretzel86}, and has been studied extensively for its connection  to chip-firing and conjugacy of Coxeter elements~\cite{EE09,Speyer09}.
The fact that equivalence classes correspond to toric chambers of the standard arrangement $\Act(\Phi_G,\Zb^n)$ is due to \cite[Theorem~1.4]{DMR16}. (Recall $\Act(\Phi_G, \widehat{\Zb A_{n-1}})$ is its essentialization.)


For the coroot lattice, Voronoi equivalence appears to be a new and perhaps equally interesting relation. It possesses several combinatorial descriptions which we discuss next.

A \emph{source-sink exchange} is an operation that transforms an acyclic orientation $\Oc$ into another $\Oc'$ by
choosing  a source vertex $i$ and a non-adjacent sink vertex $j$ of $\Oc$, and then
changing the orientation of all edges in $\Oc$ that are incident to either $i$ or $j$.
Then $i$ is a sink vertex and $j$ is a source vertex in the new orientation $\Oc'$. See \cref{fig:source-to-sink} (b).


\begin{theorem}\label{theorem: coroot Voronoi relation}
Let $L=\Zb A_{n-1}$. For $\Oc_1,\Oc_2 \in \Acyc(G)$, the following are equivalent:
\begin{enumerate}[\normalfont (i)]
\item $\Oc_1$ and  $\Oc_2$ are Voronoi equivalent.
\item $\Oc_1$ and $\Oc_2$ are related by a sequence of source-sink exchanges.
\item \label{item: coroot Voronoi relation differs by sequences of flips divisible by n} $\Oc_1$ and $\Oc_2$ are related by a sequence of source-to-sink flips of length divisible by $n$.
\item  There exists $\Oc_3 \in \Acyc(G)$ such that $\Oc_1$ and $\Oc_2$ are related to $\Oc_3$ by a sequence of source-to-sink flips of the same length.
\end{enumerate}
\end{theorem}

\begin{figure}[!h]
\centering
   \includegraphics[width=0.9 \linewidth]{figures/Comparison_of_Voronoi_equivalence}
\caption{Comparison between two Voronoi equivalences.}
\label{figure: Comparison between two Voronoi equivalences}
\end{figure}

There is also an interesting description of this relation in terms of \emph{modular flows} on $G$.
As a consequence, one has the following explicit calculations. The path with $n$ vertices has $n$ coroot Voronoi equivalence classes, and the $i$-th class has cardinality
\[
\frac{1}{2}\abs{\{ S \subseteq [n] \mid \sum_{x \in S} x \equiv i \mod n \}}.
\]
The cycle with $n$ vertices has $n(n-1)$ coroot Voronoi equivalence classes, and the $(i,j)$-th class has cardinality
\[
\abs{\{ S \subseteq [n] \mid  \abs{S}=i, \, \sum_{x \in S} x \equiv j \mod n   \}}.
\]

\printbibliography


\end{document}
